package top;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author chenyw
 * @date 2022/7/22 10:40
 */
public class Top378kthSmallest {
/*    //多路归并的思想，引入优先队列降低实践复杂度； 用到了题目中每一行有序的特点，但是没用到每一列也有序
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        //优先队列
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            //将最小的弹出，然后将它右边的元素放进去
            int[] poll = queue.poll();
            if (poll[2] != n - 1) {
                queue.offer(new int[]{matrix[poll[1]][poll[2] + 1], poll[1], poll[2] + 1});
            }
        }
        return queue.poll()[0];
    }*/

    //二分法，完全用到了题目中的所有条件，即每一列和每一行都有序
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[][] matrix, int mid, int k, int n) {
        //从左下角开始遍历
        int i = n - 1;
        int j = 0;
        //num用来统计已经遍历了多少个元素，也就是已经确定了多少元素是小于mid的
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
}
